package com.lihepeng.leecode.tree;

/**
 * 前缀树 练习版本
 * 每个节点中保存了子节点出现的所有可能
 * 插入字符串
 *  子节点存在 沿着指针移动到子节点 处理下面的字符
 *  子节点不存在 创建新的子节点 记录children 的对应位置
 *
 */
public class Trie01 {
    private Trie01 [] children;
    private boolean isEnd;
    public Trie01() {
        children = new Trie01[26];
        isEnd = false;
    }

    /**
     * 插入数据
     * @param word
     */
    public void insert(String word) {
        Trie01 node = this;
        for (int i=0;i<word.length();i++) {
            char c = word.charAt(i);
            int index = c-'a';
            if (node.children[index] ==null) {
                node.children[index] = new Trie01();
            }
            node = node.children[index];
        }
        node.isEnd =true;
    }

    /**
     * 查找数据
     * @param word
     * @return
     */
    public boolean search(String word) {
        Trie01 trie01 = this.searchPrefix(word);
        return trie01!=null && trie01.isEnd ;
    }
    private Trie01 searchPrefix(String prefix){
        Trie01 trie01 = this;
        for (int i=0;i<prefix.length();i++) {
            char c = prefix.charAt(i);
            int index = c-'a';
            if (trie01.children[index] ==null){
                // 不含有该前缀
                return null;
            }
            trie01= trie01.children[index];
        }
        return trie01;
    }

    public boolean startsWith(String prefix) {
        return this.searchPrefix(prefix)!=null;
    }
}
